/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -2;
	treeHeight = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	m_mode = mode;

	int retVal = pf.open(indexname, mode);
	if(retVal != 0) return retVal;

	//write values in
	if (mode == 'r')
	{
		//read in values 
		char tempBuf[PageFile::PAGE_SIZE];
		retVal = pf.read(0, tempBuf);
		if(retVal != 0) return retVal;

		memcpy(&treeHeight, tempBuf, sizeof(int));
		memcpy(&rootPid, tempBuf+sizeof(int), sizeof(PageId));

		memcpy(&min_key, tempBuf+sizeof(int)+sizeof(PageId), sizeof(int));
		memcpy(&max_key, tempBuf+sizeof(int)+sizeof(PageId)+sizeof(int), sizeof(int));
	}

	//if mode == 'w' and ok
    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{

	if(m_mode == 'w')
	{
		char tempBuf[PageFile::PAGE_SIZE];
		memset(tempBuf, 0, PageFile::PAGE_SIZE);

		memcpy(tempBuf, &treeHeight, sizeof(int));
		memcpy(tempBuf+sizeof(int), &rootPid, sizeof(PageId));

		memcpy(tempBuf+sizeof(int)+sizeof(PageId), &min_key, sizeof(int));
		memcpy(tempBuf+sizeof(int)+sizeof(PageId)+sizeof(int), &max_key, sizeof(int));

		int retVal = pf.write(0, tempBuf);
		if(retVal != 0) return retVal;
	}

    return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    IndexCursor cursor;
    BTLeafNode leaf;  
	if(treeHeight == -1)
    { 	
		char tempBuf[PageFile::PAGE_SIZE];
		memset(tempBuf, 0, PageFile::PAGE_SIZE);

		memcpy(tempBuf, &treeHeight, sizeof(int));
		memcpy(tempBuf+sizeof(int), &rootPid, sizeof(PageId));

		int retVal = pf.write(0, tempBuf);
		if(retVal != 0) return retVal;
		
        min_key = key;
        max_key = key;
        treeHeight++;
		leaf.insert(key, rid);

        if(leaf.write(pf.endPid(), pf)!=0)
          return RC_FILE_WRITE_FAILED;
        rootPid = pf.endPid()-1;

        return 0;
    }

    if(locate(key, cursor)!=0)
    {
		;
    }

    if(key < min_key)
      min_key = key;
	if(key > max_key)
	  max_key = key;

    if(leaf.read(cursor.pid, pf)!=0) 
      return RC_FILE_READ_FAILED;
    if(leaf.insert(key, rid) == 0)
    {
      if(leaf.write(cursor.pid, pf)!=0)
        return RC_FILE_WRITE_FAILED;
    }
    else
    {
      BTLeafNode sibleaf;//split node;
	  
	  sibleaf.setNextNodePtr(pf.endPid());
      int sibkey;

	  leaf.insertAndSplit(key, rid, sibleaf, sibkey);
	 
      if(leaf.write(cursor.pid, pf)!=0)
	  {
        return RC_FILE_WRITE_FAILED;
	  }

      if(sibleaf.write(pf.endPid(), pf)!=0)
        return RC_FILE_WRITE_FAILED;

    //dont really wanna think bout recursing. loop instead.
      if(treeHeight == 0)
      {

        BTNonLeafNode root;
        root.initializeRoot(cursor.pid, sibkey, pf.endPid()-1);
		PageId initial = pf.endPid();
        if(root.write(pf.endPid(), pf))
          return RC_FILE_WRITE_FAILED;
        rootPid = pf.endPid()-1;

        treeHeight++;
        goto end;
      }

      BTNonLeafNode nonleaf, sibnonleaf;
      PageId p, op;
      bool loop = true;
      int mid;

	  int checkgetLast = m_listNodes->getLast(p);

      if(nonleaf.read(p, pf))
        return RC_FILE_READ_FAILED;


      if(nonleaf.insert(sibkey, pf.endPid()-1) == 0)
      {
        if(nonleaf.write(p, pf)!=0)
          return RC_FILE_WRITE_FAILED;
        loop = false;
		goto end;
      }
      else
      {
		  int retV;

		  retV = nonleaf.insertAndSplit(sibkey, pf.endPid()-1, sibnonleaf, mid);
		  if(retV != 0)
			  return retV;
        if(sibnonleaf.write(pf.endPid(), pf)!=0)
          return RC_FILE_WRITE_FAILED;
		if(nonleaf.write(p, pf)!=0)
	      return RC_FILE_WRITE_FAILED;
		if(p == rootPid)
		{
			BTNonLeafNode root3;
			root3.initializeRoot(p, mid, pf.endPid()-1);
			if(root3.write(pf.endPid(), pf)!=0)
				return RC_FILE_WRITE_FAILED;
			rootPid = pf.endPid()-1;
			treeHeight++;
			return 0;
		}
		while(loop && checkgetLast==0)
		{
			op = pf.endPid()-1;
			checkgetLast = m_listNodes->getLast(p);
			if(nonleaf.read(p, pf) != 0)
				return RC_FILE_READ_FAILED;
			if(nonleaf.insert(mid, op)==0)
			{
				if(nonleaf.write(p, pf)!=0)
					return RC_FILE_WRITE_FAILED;
				break;
			}
			else 
			{
				BTNonLeafNode sibnonleaf2;
				int mid2;
				retV = nonleaf.insertAndSplit(mid, op, sibnonleaf2, mid2);
				if(retV != 0) return retV;
				if(sibnonleaf2.write(pf.endPid(), pf)!=0)
					return RC_FILE_WRITE_FAILED;
				if(p == rootPid)
				{
					BTNonLeafNode root2;
					root2.initializeRoot(p, mid2, pf.endPid()-1);
					if(root2.write(pf.endPid(), pf)!=0)
						return RC_FILE_WRITE_FAILED;
					rootPid = pf.endPid()-1;
					treeHeight++;
					goto end;
				}
				if(nonleaf.write(pf.endPid(), pf)!=0)
					return RC_FILE_WRITE_FAILED;
			}
		}
      }  
    }
end:
    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    //go down index to search for leaf-node index entry
	//look at each Node w/ pid pf

	m_listNodes = NULL;
	m_listNodes = new NodeList();

	int retVal = 0;

	//check treeHeight
	//empty tree
	if(treeHeight == -1)
	{
		return RC_NO_SUCH_RECORD;
	}

	//root node only
	//root is leaf node
	else if (treeHeight == 0)
	{
		BTLeafNode rootNode;
		if(rootPid == 0) return RC_NO_SUCH_RECORD;
		retVal = rootNode.read(rootPid, pf);
		if(retVal != 0) return retVal;

		int eid = 0;
		retVal = rootNode.locate(searchKey, eid);
		
		m_listNodes->insert(rootPid);

		cursor.pid = rootPid;
		cursor.eid = eid;

		if(retVal != 0) return retVal;

	}
	//otherwise
	//there are some non-leaf nodes and leaf nodes
	//also need to trace path for insert function 
	else
	{
		//start with root node
		BTNonLeafNode nonLeafNode;

		PageId curPid = rootPid;

		char tempBuf[PageFile::PAGE_SIZE];
		bool isLeaf = false;

		//find node to leaf
		while(!isLeaf)
		{
			if(curPid == 0)
			{
				return RC_NO_SUCH_RECORD;
			}

			m_listNodes->insert(curPid);

			retVal = nonLeafNode.read(curPid, pf);
			
			if(retVal != 0) return retVal;

			//look in node
			retVal = nonLeafNode.locateChildPtr(searchKey, curPid);
			if(retVal != 0) return retVal;

			//check is next node is a leaf or not
			retVal = pf.read(curPid, tempBuf);
			if(retVal != 0) return retVal;
			
			memcpy(&isLeaf, tempBuf, sizeof(bool));
			
		}

		//read leaf node
		BTLeafNode leafNode;
		if(curPid == 0) return RC_NO_SUCH_RECORD;

		retVal = leafNode.read(curPid, pf);
		if(retVal != 0) return retVal;

		int eid = 0;
		retVal = leafNode.locate(searchKey, eid);
		
		cursor.pid = curPid;
		cursor.eid = eid;
		
		if(retVal != 0)
			return retVal;
	}

	return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode tempLeaf;

	int retVal = tempLeaf.read(cursor.pid, pf);
	if(retVal != 0) return retVal;
	retVal = tempLeaf.readEntry(cursor.eid, key, rid);
	if(retVal != 0) return retVal;
	
	//move cursor forward to next leaf, the first entry there
	if (cursor.eid == (tempLeaf.getKeyCount()))
	{
		return RC_END_OF_TREE;
	}
	else if(cursor.eid == (tempLeaf.getKeyCount()-1))
	{			
		PageId tempPid = tempLeaf.getNextNodePtr();

		cursor.eid = 0;
		cursor.pid = tempPid;

	}
	//stay in node, more to next entry
	else
	{
		cursor.eid++;
	}

	//if goes to next node
		//also check if next node is null
	//else go to next item on list

    return 0;
}
